package club.xiaojiawei.binarytree;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/13/22 5:14 PM
 * @question 222. 完全二叉树的节点个数
 * @description 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 */
public class CountNodes222 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(3);
        left.left = new TreeNode(4);
        left.right = new TreeNode(5);
        right.left = new TreeNode(6);
        root.left = left;
        root.right = right;
        int result = countNodes3(root);
        System.out.println("节点数："+result);
    }

    /**
     * 递归+DFS（部分遍历）
     * @param root
     * @return
     */
    public static int countNodes(TreeNode root) {
        int height = height(root);
        int[] count = {(1 << height) - 1};
        recursion(root, height, 0, count);
        return count[0];
    }

    public static int height(TreeNode root){
        return root == null? 0 : height(root.left) + 1;
    }

    public static boolean recursion(TreeNode node, int height, int depth, int[] count){
        if (node == null){
            if (depth == height){
                return true;
            }else {
                count[0]--;
                return false;
            }
        }
        if (recursion(node.right, height, ++depth, count)){
            return true;
        }
        return recursion(node.left, height, depth, count);
    }

    /**
     * 民间-递归+DFS（全部遍历）
     * 平均时间复杂度O(n)
     * @param root
     * @return
     */
    public static int countNodes2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = countNodes2(root.left);
        int right = countNodes2(root.right);
        return left+right+1;
    }

    /**
     * 官方-二分查找+位运算(nb)
     * @param root
     * @return
     */
    public static int countNodes3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int level = 0;
        TreeNode node = root;
        while (node.left != null) {
            level++;
            node = node.left;
        }
        int low = 1 << level, high = (1 << (level + 1)) - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public static boolean exists(TreeNode root, int level, int k) {
        int bits = 1 << (level - 1);
        TreeNode node = root;
        while (node != null && bits > 0) {
            if ((bits & k) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
